This invention relates to data encrypting and decrypting apparatus and to data encrypting and decrypting methods. It relates particularly but not exclusively to cryptographic systems which use variable keys, systems which use variable length data blocks, and systems which use variable encrypting and decrypting algorithms.
Cryptography typically involves converting data from an understandable form into an encrypted form which cannot be understood by persons other than the intended recipient, and transmitting the data to the recipient who deciphers the data. It is useful in many applications, including confidential business communications, Internet commerce, military intelligence, and electronic financial services. In each of these applications, it is essential that communications be secure against eavesdropping and unauthorised access.
Encryption of data is usually accomplished by applying an algorithm to that data, and decryption is accomplished by applying the inverse of that algorithm. In many cases, the encryption step involves a xe2x80x9cpass phrasexe2x80x9d or key, which is combined with the data according to the algorithm to create the encrypted message, so that it is necessary for the recipient to know both the key and the inverse algorithm in order to decrypt the message.
Cryptography typically serves two purposes. One of these is to ensure that only the intended recipient receives a secret message. This is accomplished by ensuring that only the intended recipient has the key and inverse algorithm necessary to decrypt the message. The other purpose is xe2x80x9cmessage authenticationxe2x80x9d, which provides assurance to the recipient that the message really did come from the sender. This is accomplished by ensuring that only the sender has the key and algorithm necessary to encrypt messages which make sense when decrypted by the key and inverse algorithm.
One common form of cryptography is public key cryptography, as described in U.S. Pat. Nos.4,218,582 and 4,200,770 by Martin E Hellman, Bailey W Diffie and Ralph C Merkle. This involves finding a pair consisting of an algorithm and an inverse algorithm, for which it is impossible (or xe2x80x9ccomputationally infeasiblexe2x80x9d) to determine the inverse algorithm from the original algorithm. One set of such algorithm/inverse pairs is known as the RSA algorithm and is described in U.S. Pat. No. 4,405,829 by Ronald L Rivest, Adi Shamir and Leonard M Adleman. The person who creates the algorithm/inverse pair distributes the algorithm publicly but keeps the inverse secret. Anyone can then send a secret message to that person by encrypting the message with the algorithm (or xe2x80x9cpublic keyxe2x80x9d). Only the person with the inverse algorithm (or xe2x80x9csecret keyxe2x80x9d) can decrypt any such message. Conversely, message authentication can be achieved if the person encrypts a message with the secret key. Any other person can use the public key to decrypt the message and confirm that it came from the secret key holder.
Public key cryptography is susceptible to xe2x80x9cspoofingxe2x80x9d, in which a person pretends to be someone else, and sends out a public key under that other person""s name. Moreover, because the algorithm/inverse pairs tend to be complex, this method of cryptography typically requires considerable computing resources and is comparatively slow.
Another common type of cryptography is known as DES. This is a block cipher which is the US Data Encryption Standard. A block cipher involves partitioning the message into blocks, perhaps with some padding to fill out the final block, and then encrypting and transmitting each block. DES uses a 64-bit block with a 56-bit key. DES is one of many different types of secret key cryptography, which depends upon the secret key being sent by a secured channel from the transmitter to the receiver so that it is kept secret from the rest of the world.
There are various different ways in which a person may attempt to break an encryption code without first having had access to the key and/or algorithm. One of these approaches is known as the xe2x80x9ccodebook attackxe2x80x9d, and it involves building a codebook of all possible transformations between original message text and encrypted data. This approach can work if there are patterns in the encrypted data which correspond with patterns in the message text. A codebook attack can in some instances be effective against DES cryptography.
An object of the present invention is to provide a new cryptographic method. Another object is to provide a cryptographic method which is less computationally intensive than methods based on current methods like the DES and RSA algorithms. Another object is to provide a cryptographic method which is more secure and flexible. Another object is to facilitate the transmission of data securely in real time with minimum delay or latency.
According to a first aspect of the invention, a method of encrypting data includes the following steps:
(a) creating or selecting a master key;
(b) segmenting the data into data blocks of equal or variable lengths;
(c) for each data block selecting a sub-key of arbitrary starting position and of matched or unmatched length from the master key; and
(d) encrypting each data block using its sub-key and a selected or associated encryption algorithm.
When an encrypted message is to be sent to a recipient, it is preferred that the master key be kept secret and provided to the recipient by a secured channel. However, this is not essential, as the master key can be public if the sub-keys or sub-key selection process are kept secret.
The master key may be created or selected in any suitable manner. It may consist of a pass phrase, or it may be generated from a pass phrase according to an algorithm which is available to both message sender and receiver.
The master key or pass phrase may also be a file or file seriesxe2x80x94text, graphic, image, audio, movie, multimedia or any binary file. Where the master key is a binary file, the file may be one that is in private, restricted, limited or closed distribution. This file might be a file that is linked to a user or group, such as a binary file containing finger-print, voice, image or other user-specific and/or user property information.
In cases where the binary file is readily and publicly available, it may be in the form of a public key or pass phrase, as described above. It can also be a multimedia file, containing data for a movie, video, image, audio, graphics, or a large text file or a non-alphabetic-based language file (e.g. Japanese, Chinese, Middle Eastern, etc.) represented in a format that is readable to the system. The binary file can also be a common file that is part of the operating system or an application program.
Binary files of these types, although easily accessible, typically are large in volume (Kbyte to Mbytes). They can be downloaded from a site on the network or transferred via some other means, secured or otherwise. This downloading might be done on a periodic basisxe2x80x94monthly, weekly, daily or even hourly, or aperiodically, as and when needed.
The master key, if added security be needed, can be amended or replaced in the midst of its use. This event might be triggered by an algorithm.
The step of segmenting data into blocks may involve separating the data into equally-sized blocks, as occurs in the DES method, or it may involve separating the data into data blocks of variable arbitrary length. The use of variable length data blocks is preferred because it increases the degree of difficulty in attacking the encryption system, particularly if the length of each data block when encrypted bears no relationship to the length of the data block before encryption.
Sub-keys may all be of the same length, but it is preferred for the sake of maximising security that they be of variable length. They may be a selection of contiguous bits from the master key, or they may comprise non-contiguous bits determined according to a pre-arranged pattern, such as every second bit from the sub-key start position, or skipping every third byte, etc. It is preferred for the sake of convenience that sub-keys be comprised of contiguous bits.
The step of selecting a sub-key from the master key may involve selecting a sub-key starting position from a pre-defined set of arbitrary positions and selecting a sub-key length from a pre-defined set of arbitrary lengths. Thus, for example, there may be a table of randomly-selected starting positions and a table of randomly-selected lengths. Sub-key selection may proceed simply by moving through the table in linear sequence. Variations include changing sub-key only on every second or third data block, skipping every second table entry, etc. In arrangements where sub-key selection proceeds in order through a pre-defined table, provided the message sender and receiver already both have the same tables, there is no need for communicating the particular selections for starting positions and lengths for each data block. Alternatively, instead of moving through the table in sequence, sub-key selection may involve choosing random numbers n and m, where n designates the nth entry in the first table and m designates the mth entry in the second table. In this arrangement, the tables form part of a seed (preferably secret) which has previously been created and shared between message sender and recipient. The message sender can let the receiver know the sub-key simply by specifying (n,m), and the receiver extracts the sub-key from the master key by locating the nth entry in the starting position table and the mth entry in the length table from the seed, and applying those values to the master key.
A sub-key start position is an indicator of the number of bits or bytes (or other data units) which are ignored in the master key before data is taken for the sub-key. The sub-key length is a measure of the number of bits or bytes (or other data units) which are taken from the master key for use in the sub-key, starting from the sub-key start position. If a sub-key length is longer than the amount of data in the master key after the sub-key start position, the master key can xe2x80x9cwrapxe2x80x9d, so that the remaining data for the sub-key is obtained from the start of the master key.
In the invention as it has been described so far, different data blocks are encrypted by reference to different sub-keys. Security can be further enhanced by also using different algorithms for encrypting different data blocks. This makes attacks particularly difficult because the attacker must identify not only a separate sub-key for each data block but also a separate algorithm. The algorithms may be any suitable types of bit manipulation, processing or encryption algorithms. An algorithm might alternatively or additionally effect an action such as a change or amendment in the master key (which may be conditional or otherwise, in part or in whole), with the change or amendment occurring during the encryption/decryption process.
A set of algorithms may be identified and stored in a randomly ordered table in a seed together with a sub-key start position table and a sub-key length table, as described above. Different or replicated algorithms may be used for different data blocks simply by progressing through the table in linear or parallel fashion one at a time, or in some predetermined pattern such as changing algorithm for every third data block or skipping every fourth algorithm. Alternatively, and more preferably, different algorithms are selected from the table in an arbitrary order. In this arrangement, where the seed has earlier been communicated to the receiver via a secured channel, the message sender can identify the sub-key and algorithm for each data block in the simple format (n,m,p) where n indicates the nth entry in the sub-key start position table, m indicates the mth entry in the sub-key length table, and p indicates the pth entry in the algorithms table.
Where a seed is used as well as a master key, it is only necessary for either the seed or the master key to be kept secret. The master key could be made public, or readily available to the public, such as an image or movie archive file from a widely accessible web site, and persons other than the intended recipient would still be unable to determine the particular sub-keys and/or algorithms used in encrypting a particular message. Alternatively, the seed could be made public, and persons other than the intended recipient would be unable to determine the master key. For increased security, it is preferred that both the master key and the seed be kept secret.
According to a second aspect of the invention, a method of encrypting data includes the following steps:
(a) creating or selecting a master key;
(b) segmenting the data into data blocks of equal or variable lengths;
(c) for each data block selecting an encryption algorithm;
(d) encrypting each data block using its encryption algorithm.
As has been described above, the encryption algorithm selected for each data block may be selected from a pre-defined set or sub-set of suitable algorithms. The pre-defined set may consist of a table, so that the pth algorithm in a table can be identified in a message simply as (p), without disclosing to an interceptor any information about the nature of the algorithm itself. Such a table preferably has been communicated securely previously, or forms part of a seed which has previously been communicated secretly between the message sender and receiver. Alternatively, the seed may be communicated via a secret communication channel after the actual message has been communicated, or, less preferably, the seed may be communicated as part of the message transmission.
According to a third aspect of the invention, a method of communicating data in a secure manner from a message transmitter to a message receiver includes the following steps:
(a) creating a seed which includes a set of arbitrary sub-key start positions, a set of arbitrary sub-key lengths, and a set of suitable encryption algorithms;
(b) communicating the seed to the message receiver over a secured channel;
(c) creating or selecting a master key;
(d) communicating the master key to the message receiver over a secured channel;
(e) dividing the data into data blocks of arbitrary equal or variable length;
(f) for each data block, selecting from the seed a sub-key start position, a sub-key length (which may be matched or unmatched in length to the corresponding data block), and an encryption algorithm;
(g) using the sub-key start position and length for each data block to derive from the master key a sub-key for that data block;
(h) encrypting each data block using that data block""s sub-key and encryption algorithm;
(i) transmitting each encrypted data block to the receiver together with a sub-key start position index number, sub-key length index number and encryption algorithm index number for each data block, enabling the receiver to derive the appropriate sub-key and encryption algorithm and thereby to decrypt the data block.
The seed may be communicated to the message receiver over any suitable type of secured channel. One way of doing this is over a public key cryptography system. Given that many messages may be sent using the one seed, the additional computing resources used in sending the seed in this manner may be justified. Another way of doing this is via a physical delivery by a courier of the seed on computer storage media or in printed form. It will be appreciated that there are numerous other possible types of secured channels.
The master key may also be communicated over any suitable type of secured channel. It is especially preferred, for the sake of added security, that different secured channels, or at least different times of delivery, be used for the master key and the seed. In one suitable arrangement, the master key may be based on a pass phrase. The pass phrase may be combined with part or all of the seed according to a predetermined algorithm to generate the master key. In this case, the secured channel chosen to communicate the pass phrase may be a telephone call, with the pass phrase being spoken.
According to a fourth aspect of the invention, apparatus for encrypting data includes:
(a) a data block creating processor, which accepts a stream of data as its input, and outputs the data in the form of blocks;
(b) a random selector, which selects a sub-key start position and a sub-key length;
(c) a sub-key selector, which accepts as inputs a master key, the sub-key start position and sub-key length, and derives from these a sub-key;
(d) an encryption processor, which accepts as inputs a sub-key and a data block (not necessarily of matched length), and uses the sub-key to encrypt the data block according to an encryption algorithm.
The data block creating apparatus may operate in any suitable manner. It may create data blocks of fixed or random lengths, with random lengths being especially preferred, for the reasons discussed above.
The random selector may operate in any suitable manner. It may select a sub-key start position and sub-key length directly, or, more preferably, it may select these by randomly selecting table entry numbers, where selections of pre-defined suitable start positions and lengths have previously been entered in randomly-ordered tables. Thus the sub-key can be defined concisely by two table entry numbers, which themselves bear no resemblance to the sub-key start position or length values.
It is preferred that the random selector also selects an encryption algorithm from a group of suitable algorithms. In such arrangements, the encryption processor may accept the encryption algorithm as one of its inputs. Alternatively, the apparatus may further include a plurality of encryption processors, each embodying an encryption algorithm, wherein the random selector also selects an encryption processor, with the selected encryption processor being the processor which encrypts the data block according to its encryption algorithm.
According to a fifth aspect of the invention, apparatus for encrypting data includes:
(a) a data block creating processor, which accepts a stream of data as its input, and outputs the data in the form of blocks;
(b) a plurality of encryption processors, each embodying an encryption algorithm; and
(c) a random selector, which selects one of the encryption processors, so that the selected encryption processor encrypts the data block according to its encryption algorithm.
According to a sixth aspect of the invention, apparatus for encrypting data includes:
(a) a data block creating processor, which accepts a stream of data as its input, and outputs the data in the form of blocks;
(b) a random selector, which selects an encryption algorithm from a group of suitable algorithm;
(c) an encryption processor, which accepts as inputs the encryption algorithm and the data block, and uses the encryption algorithm to encrypt the data block.
According to a seventh aspect of the invention, apparatus for communicating data in a secure manner from a message transmitter to a message receiver, includes:
(a) a data block creating processor, which accepts a stream of data as its input, and outputs the data in the form of blocks;
(b) a random selector, which selects a sub-key start position, a sub-key length, and an encryption algorithm;
(c) a sub-key selector, which accepts as inputs a master key, the sub-key start position and sub-key length, and derives from these a sub-key;
(e) an encryption processor, which accepts as inputs a sub-key, an encryption algorithm and a data block, and uses the sub-key to encrypt the data block according to the encryption algorithm; and
(f) apparatus for transmitting each encrypted data block to the receiver together with a sub-key start position index number, sub-key length index number and encryption algorithm index number for each data block, enabling the receiver to derive the appropriate sub-key and encryption algorithm and thereby to decrypt the data block.
According to an eighth aspect of the invention, apparatus for communicating data in a secure manner from a message transmitter to a message receiver, includes:
(a) a data block creating processor, which accepts a stream of data as its input, and outputs the data in the form of blocks;
(b) a plurality of encryption processors, each embodying an encryption algorithm, and each of which accepts as inputs a sub-key and a data block, and uses the sub-key to encrypt the data block according to its algorithm;
(c) a random selector, which selects, for each data block, a sub-key start position, a sub-key length, and an encryption processor;
(d) a sub-key selector, which accepts as inputs a master key, the sub-key start position and sub-key length, and derives from these a sub-key;
(e) apparatus for transmitting each encrypted data block to the receiver together with a sub-key start position index number, sub-key length index number and encryption algorithm index number for each data block, enabling the receiver to derive the appropriate sub-key and encryption algorithm and thereby to decrypt the data block.
It will be appreciated that the invention is suitable for the generation of digital signatures. A digital signature is a portion of code appended to a digital document or used to encode the document or a part thereof, in order to prove to the recipient that the document is a genuine communication from the person or organisation who applied the digital signature. If only the receiver and the sender have access to a secret encryption and decryption process, and the receiver receives a validly encoded message, the receiver can be certain that the message was sent by the sender. Digital signatures are important in fields such as electronic commerce, where it is necessary to make legally binding electronic transactions.
The invention will hereinafter be described in greater detail by reference to the attached drawings which show an example form of the invention. It is to be understood that the particularity of those drawings does not supersede the generality of the preceding description of the invention.
FIG. 1 is a flow chart of an encryption process according to an embodiment of the invention.
FIG. 2 is a schematic illustration of the contents of a seed for use in the process of FIG. 1.
FIG. 3 is an explanatory illustration of the operation of the sub-key parts of the seed of FIG. 2.
FIG. 4 illustrates the extraction of a sub-key from a master key in the process of FIG. 1.
FIG. 5 illustrates the principle of multiple xe2x80x9choppingxe2x80x9d sub-keys extracted from the master key in the process of FIG. 1.
FIG. 6 is a further graphical illustration of multiple xe2x80x9choppingxe2x80x9d sub-keys extracted from the master key.
FIG. 7 is an explanatory illustration of the operation of the securithm numbers part of the ed of FIG. 2.
FIG. 8 is a graphical illustration of multiple xe2x80x9choppingxe2x80x9d securithms in the process of FIG. 1.
FIG. 9 is a step-by-step illustration of the encryption of one data block in the process FIG. 1.
FIG. 10 provides a more detailed explanation of one of the algorithm steps of FIG. 9.
FIG. 11 illustrates the correspondence between data blocks in the original message and data blocks in the encrypted message.
FIG. 12 is a schematic illustration of generic apparatus suitable for accomplishing the process of FIG. 1.
FIG. 13 is a schematic diagram of the inputs and outputs of the encrypting process of FIG. 1 and a corresponding decrypting process.